//
// Created by Incredible on 17/3/16.
//

#ifndef HEAPSORT_QUICKSORT_H
#define HEAPSORT_QUICKSORT_H

/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param l
 * @param r
 */

#include <iostream>
#include "InsertionSort.h"

template<typename T>
void __quickSort3Ways(T arr[], int l, int r) {

    if (r - l <= 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    //partition3Ways
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;         //arr[l+1, lt] < v
    int gt = r + 1;     //arr[gt, r] > v
    int i = l + 1;      //arr[lt+1, i) == v

    while (i < gt) {

        if (arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else if (arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            lt++;
            i++;
        } else {
            i++;
        }
    }

    //交换标识位置到其应该存在的位置
    swap(arr[l], arr[lt]);

    __quickSort3Ways(arr, l, lt - 1);
    __quickSort3Ways(arr, gt, r);

}

/**
 * 3路快速排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void quickSort3Ways(T arr[], int n) {

    srand(time(NULL));
    __quickSort3Ways(arr, 0, n - 1);
}

#endif //HEAPSORT_QUICKSORT_H
